public class myecs {
    public class cutNode{
        public String val;
        public cutNode left;
        public cutNode rigth;

        public cutNode(String val) {
            this.val = val;
        }
    }
    public cutNode newecs(){
        cutNode cutNode1=new cutNode("A");
        cutNode cutNode2=new cutNode("B");
        cutNode cutNode3=new cutNode("C");
        cutNode cutNode4=new cutNode("D");
        cutNode cutNode5=new cutNode("E");
        cutNode cutNode6=new cutNode("F");
        cutNode1.left=cutNode2;
        cutNode1.rigth=cutNode3;
        cutNode2.left=cutNode4;
        cutNode2.rigth=cutNode5;
        cutNode3.left=cutNode6;
        return cutNode1;
    }
    public void qian(cutNode CutNode){
        if(CutNode ==null){
            return;
        }
        System.out.print(CutNode.val+" ");
        qian(CutNode.left);
        qian(CutNode.rigth);
    }
    public void zhong(cutNode CutNode){
        if(CutNode ==null){
            return;
        }
        qian(CutNode.left);
        System.out.print(CutNode.val+" ");
        qian(CutNode.rigth);
    }
    public void huo(cutNode CutNode){
        if(CutNode ==null){
            return;
        }
        qian(CutNode.left);
        qian(CutNode.rigth);
        System.out.print(CutNode.val+" ");
    }
    //获取节点数量
    public int jiesum1(cutNode Cut){
        if(Cut==null){
            return 0;
        }
        return jiesum1(Cut.left)+jiesum1(Cut.rigth)+1;
    }

    public int size;
    public void jiesum2(cutNode Cut){
        if(Cut==null) return;
        size++;
        jiesum2(Cut.left);
        jiesum2(Cut.rigth);
    }
    //获取叶子的数量
    public int ksum1(cutNode Cut) {
        if (Cut == null) {
            return 0;
        }
        if (Cut.left == null && Cut.rigth == null) {
            return 1;//计数法
        }
        return ksum1(Cut.rigth) + ksum1(Cut.left);
    }
    //第k层的结点数量
    public int osum1(cutNode Cut,int k){
        if(Cut==null) return 0;
        if(k==1){
            return 1;
        }
        return osum1(Cut.left,k-1)+osum1(Cut.rigth,k-1);
    }
    //获取⼆叉树的⾼度
    public int hight(cutNode Cut){
        if(Cut==null){
            return 0;
        }
        int highleft=hight(Cut.left);
        int highrigth=hight(Cut.rigth);
        return Math.max(highleft,highrigth)+1;
    }
    //检查tim是否存在
    public cutNode find(cutNode Cut,String tim){
        if(Cut==null){
            return null;
        }
        if(Cut.val.equals(tim)){
            return Cut;
        }
        cutNode li=find(Cut.left,tim);
        if(li!=null){
            return li;
        }
        cutNode ri=find(Cut.rigth,tim);
        if(ri!=null){
            return ri;
        }
        return null;
    }

    public static void main(String[] args) {
        myecs my=new myecs();
        cutNode to=my.newecs();
        my.qian(my.newecs());
        System.out.println();
        my.zhong(my.newecs());
        System.out.println();
        my.huo(my.newecs());
        System.out.println();
        System.out.println("获取节点数量");
        System.out.println(my.jiesum1(to));
        my.jiesum2(to);
        System.out.println(my.size);
        System.out.println("获取叶子的数量");
        System.out.println(my.ksum1(to));
        System.out.println("第k层的叶子数量");
        System.out.println(my.osum1(to,3));
        System.out.println("获取⼆叉树的⾼度");
        System.out.println(my.hight(to));
        System.out.println("检查tim是否存在");
        System.out.println(my.find(to,"B").val);
    }
}
